/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package proyectofinal_diseno;
   
import java.util.*;
/**
 * @author Katherine Vargas
 * @author Esteban Herrera
 */

public class Backtracking {
	
	static int n;	
	public int [][] Laberinto= new int[n][n];
	public int [][] Solucion= new int[n][n];
	private static Backtracking bac;
	public int x=0,y=0;
	public String Orden;
	public int control=1;
	public String Ter="Inicia";
	public int valor=1;

	static void ejecuta(int num) {
		Backtracking.n= num;
		bac = new Backtracking();		
		bac.llenar_matriz();
		bac.imprimir();
		bac.camino();
		System.out.println("\n"+"SALIDA DEL LABERINTO ES: \n");
		bac.imprimir_solucion();
	}
	
	public void llenar_matriz(){		
		
		Random rnd = new Random();
		for (int i=0; i<Laberinto.length;i++){
			for (int j=0; j<Laberinto.length;j++){
		Laberinto[i][j] = rnd.nextInt(2);
		Solucion [i][j]=0;
		}
	  }		
		Laberinto[0][0]=1;
		Laberinto[n-1][n-1]=1;
	}
	
	public void imprimir()
        {	
            for (int i=0; i<Laberinto.length;i++)
            {
                System.out.print("\n");
		for (int j=0; j<Laberinto.length;j++)
                {
                    System.out.print(Laberinto[i][j]+" ");
                }
            }
            System.out.println("");
	}
	
	public void camino()
        {
            while(Ter.equals("Inicia"))
            {
                if(x+1>=n && Laberinto[x][y+1]==0) 
                {
                    Laberinto[x][y]=0;
                }
                if(y+1>=n && Laberinto[x+1][y]==0) 
                {
                    Laberinto[x][y]=0;
                }
                if(x+control>=n) 
                {
                    control=0;
                }	
                if(y+control>=n) 
                {
                    control=0;
                }	
                if(Laberinto[x+control][y]==0 && Laberinto[x][y+control]==0 )
                {				
                    Laberinto[x][y]=0;
                    Solucion[x][y]=0;
                    control=1;		
                    if(x==0 && y==0)
                    {
                        Laberinto[x][y]=1;
                    }
                    movimientos_posibles();				
                }else
                {
                    control=1;
                    Solucion[x][y]=1;
                    movimientos_posibles();
                }
                    if(x==n-1 && y==n-1) 
                    {
                        Ter="Finaliza";
                    }
            }
        }
	
	public String movimientos_posibles(){
		Orden="null";
		while("null".equals(Orden)){
						
			
		if (x+1<n && x+1>=0 && Laberinto[x+1][y]==1){
			x=x+1;
			Orden="Abajo";
			break;
		}
		if (y+1<n && y+1>=0 && Laberinto[x][y+1]==1){
			y=y+1;
			Orden="Derecha";
			break;
		}
		
		if (y-1>=0 && Laberinto[x][y-1]==1){
			y=y-1;
			Orden="Izquierda";
			break;
		}
		if (x-1>=0 && Laberinto[x-1][y]==1){
			x=x-1;
			Orden="Arriba";
			break;
		}
		
		if(x-1<0 && y-1<0){
			System.out.println("\n"+"No Hay Salida");
			//imprimir();
			System.exit(0);
		}	
		
		if(y<n){
			x=0;
			y=0;
		}
		
		
	}
		return Orden;
	}
	
	
	public void imprimir_solucion(){	
		Solucion[n-1][n-1]=1;
		for (int i=0; i<Solucion.length;i++){
			System.out.print("\n");
			for (int j=0; j<Solucion.length;j++){
				System.out.print(Solucion[i][j]+" ");
	
			}
		}
                System.out.print("\n");
	}
}

